package com.github.hgkmail.hello.leetcode101.firstsearch;

import java.util.Arrays;

//一个格子，4条边，若边的旁边是水或者边界，周长+1；若边的旁边是陆地，周长+0。
public class LC463IslandPerimeter {
    //helper
    public int findPerimeter(int[][] grid, int[][] visited, int i, int j) {
        //boundary
        if (i<0 || i>=grid.length || j<0 || j>=grid[0].length || visited[i][j]==1) { //visited[i][j]写成visited[i][i]，导致死循环，call stack溢出。。。
            return 0;
        }
        visited[i][j]=1;
        if (grid[i][j]==0) {
            return 0;
        }
        int p=0;
        //计算周长
        if (i-1<0 || grid[i-1][j]==0) p++;
        if (i+1>=grid.length || grid[i+1][j]==0) p++;
        if (j-1<0 || grid[i][j-1]==0) p++;
        if (j+1>= grid[0].length || grid[i][j+1]==0) p++; //这里j是对应grid[0].length，别写成grid.length。。。
        //四个方向，递归
        p += findPerimeter(grid, visited, i-1, j)+findPerimeter(grid, visited, i+1, j)
                +findPerimeter(grid, visited, i, j-1)+findPerimeter(grid, visited, i, j+1);

        return p;
    }

    //main
    public int islandPerimeter(int[][] grid) {
        //base case
        if (grid.length<=0 || grid[0].length<=0) {
            return 0;
        }
        //global
        int[][] visited=new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                visited[i][j]=0;
            }
        }
        int maxLen=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                maxLen=Math.max(maxLen, findPerimeter(grid, visited, i, j));
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(new LC463IslandPerimeter().islandPerimeter(new int[][]{
                {1,1}
        }));
    }
}
